package com.monkeyboy.stack;

import java.util.PriorityQueue;

/**
 * 数据流中的中位数
 * <p>
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，
 * 那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值
 * ，那么中位数就是所有数值排序之后中间两个数的平均值。
 * <p>
 * 数据流中的中位数可以采用堆来处理
 * 一个堆存数据流的左边，一个堆存数据流的右边
 *
 * @Author Gavin
 * @date 2021.04.01 10:25
 */
public class Stack04 {
    private PriorityQueue<Integer> maxLeft = new PriorityQueue<>(((o1, o2) -> o2 - o1));//递减的，存放小的部分
    private PriorityQueue<Integer> minRight = new PriorityQueue<>();//递增，存放大的部分
    int n = 0;

    public void insert(Integer num) {
        if ((n & 1) == 0) {
            maxLeft.add(num);
            minRight.add(maxLeft.poll());//这里可以看出来如果为奇数那么右边的元素要多一个，这样的操作方式是为了保证大小顶推之间的数据是平衡的
        } else {
            minRight.add(num);
            maxLeft.add(minRight.poll());
        }
        n++;
    }

    public Double getCenterNumber() {
        if ((n & 1) == 0) {
            return (maxLeft.peek() + minRight.peek()) / 2.0;
        } else {
            return Double.valueOf(Integer.valueOf(minRight.peek()));
        }
    }

    public static void main(String[] args) {
        Stack04 stack04=new Stack04();
        stack04.insert(2);
        stack04.insert(3);
        stack04.insert(8);
        stack04.insert(4);
        System.out.println(stack04.getCenterNumber());
    }
}
